package leetcode_day._2021._202109._0110;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/9/8 8:55
 * IPO
 * 算法：贪心  优先队列
 * 从可以买入的项目中选择利润最大的
 * 根据 capital 从小到大排序
 * 将 capital[i] 小于 w 的放入队列中
 * 不断重复
 *
 */
public class _08_502 {

    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int n = profits.length;
        int[][] arr = new int[n][2];
        for (int i = 0; i < n; i++) {
            arr[i][0] = capital[i];
            arr[i][1] = profits[i];
        }
        Arrays.sort(arr, Comparator.comparingInt(a -> a[0]));
        PriorityQueue<Integer> queue = new PriorityQueue<>((x, y) -> y - x);
        int cur = 0;
        while (k-- > 0) {
            while (cur < n && w >= arr[cur][0]) {
                queue.offer(arr[cur][1]);
                ++cur;
            }
            if (!queue.isEmpty()) w += queue.poll();
            else break;
        }
        return w;
    }

}
